class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[n] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n, 1):
                if s[i] == s[j]:
                    dp[i][j] = dp[i][j - 1]
                else:
                    for k in range(i, j, 1):
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
        return dp[0][-1]


class Solution2:
    def strangePrinter(self, s: str) -> int:
        stack = []
        cnt = 0
        # 去除连续的字母
        for c in s:
            if not stack:
                stack.append(c)
            elif stack and stack[-1] == c:
                pass
            elif len(stack) > 1 and stack[-2] == c:
                cnt += 1
                stack.pop()
            else:
                stack.append(c)
        memo = {}

        def dp(i, j):
            if i > j:
                return 0
            if (i, j) not in memo:
                ans = dp(i + 1, j) + 1
                for k in range(i + 1, j + 1):
                    if stack[k] == stack[i]:
                        ans = min(ans, dp(i, k - 1) + dp(k + 1, j))
                memo[i, j] = ans
            return memo[i, j]

        return dp(0, len(stack) - 1) + cnt


if __name__ == '__main__':
    sol = Solution2()
    print(sol.strangePrinter("abcabc"))
    print(sol.strangePrinter("aaabbb"))
